package com.michael.tree.btree;

import javax.swing.*;
import java.util.*;

/**
 * B+树是一种多路平衡查找树
 *
 * 查找
 * 插入//key不重复
 * 删除
 * 打印
 */

public class BPlusTree {
    public class Node{
        private boolean isLeaf;
        //节点的子节点列表-非叶子节点肯定有子节点
        private List<Node> children;
        //非叶子节点键表
        private List<Integer> keyList;
        //节点键值对
        private List<KeyAndValue> keyAndValues;
        //叶子节点的后节点
        private Node nextNode=null;
        //叶子节点的前节点
        private Node preNode=null;
        //节点的父节点
        private Node fatherNode=null;

        //创建新叶子节点
        public Node(boolean a){
            if(a){
                this.keyAndValues=new LinkedList<>();
                this.isLeaf=true;
            }
            else {
                this.children=new LinkedList<>();
                this.keyList=new LinkedList<>();
                this.isLeaf=false;
            }
        }
        //-非叶子节点肯定有子节点
        public boolean isLeaf(){
            return children==null;
        }


    }
    public static class KeyAndValue{
        private int key;
        private Object value;
        private void setValue(Object value){
            this.value=value;
        }
        private KeyAndValue(int key,Object value){
            this.key=key;
            this.value=value;
        }
    }
    //排序
    public class TreeNodeComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1-o2;
        }
    }

    //成员变量
    private int order;
    private Node root=null;
    private Node head=null;
    public BPlusTree(int order){
        if(order<3){
            System.out.println("order must >2");
            System.exit(0);
        }
        this.order=order;
    }

    //查找
    private Object search(int key,Node root){
        if(root==null){
            System.out.println("树空,无查找");
            return null;
        }
        //如果是叶子节点
        if(root.isLeaf()){
            //二分查找
            int low=0,high=root.keyAndValues.size()-1,mid;
            int comp;
            while(low<=high){
                mid=(low+high)/2;
                comp=root.keyAndValues.get(mid).key-key;
                if(comp==0)
                    return root.keyAndValues.get(mid).value;
                else if(comp<0)
                    low=mid+1;
                else
                    high=mid-1;
            }
            //未找到对象
            System.out.println("键不在树中，未找到");
            return null;
        }
        /**
         *                X1| X2 | X3
         *     <X1 |  >=X1 <x2 |  >=x2  <x3| >=x3
         *     */
        //非叶子节点
        //如果key小于最左边的key,沿着第一个子节点继续搜索
        if(key-root.keyList.get(0)<0)
            return search(key,root.children.get(0));
            //如果key大于等于最右边ke'y，沿着最后一个子节点继续搜索
        else if(key-root.keyList.get(root.keyList.size()-1)>=0){
            //System.out.println(root.keyList);
            return search(key,root.children.get(root.children.size()-1));
        }
        //否则沿比key大的前一个子节点继续搜索
        else{
            //二分查找，
            int low=0,high=root.keyList.size()-1,mid=0;
            int comp;
            while(low<=high){
                mid=(low+high)/2;
                comp=root.keyList.get(mid)-key;
                if(comp==0)
                    return search(key,root.children.get(mid+1));
                else if(comp<0)
                    low=mid+1;
                else
                    high=mid-1;
            }
            return search(key,root.children.get(low));
        }

    }

    /**
     * 插入
     * 键在树中-更新value，不在-插入
     *非叶子节点子节点列表长度>order,需要分裂成两个节点（父节点增加索引）--回溯平衡
     */

    //节点中是否存在key键-存在返回下标，不存在返回-1
    private Integer isExist(Node root,int key){
        if(root==null){
            System.out.println("树空，不存在");
            return -1;
        }
        //二分法
        int low=0,high=root.keyAndValues.size()-1,mid;
        int comp;
        while(low<=high){
            mid=(low+high)/2;
            comp=root.keyAndValues.get(mid).key-key;
            if(comp==0)
                return mid;
            else if(comp<0)
                low=mid+1;
            else
                high=mid-1;
        }
        return -1;
    }
    //在不满的叶子节点插入kv---不存在相等key情况
    private void inseartInleaf(Node root,KeyAndValue kv){
        //二分查找，插入
        int low=0,high=root.keyAndValues.size()-1,mid;
        int comp;
        while(low<=high){
            mid=(low+high)/2;
            comp=root.keyAndValues.get(mid).key-kv.key;
            if(comp>0)
                high=mid-1;
            else
                low=mid+1;
        }
        root.keyAndValues.add(low,kv);
    }
    //插入--key不重复，key重复则更新value
    private void inseart(Node root,KeyAndValue kv){
        //树空，直接插入，头，根节点
        if(root==null){
            Node newNode=new Node(true);
            this.root=newNode;
            this.head=newNode;
            this.root.keyAndValues.add(kv);
            return;
        }
        //如果是叶子节点
        if(root.isLeaf()){
            //System.out.println("219- 叶子加节点添加");
            int index=isExist(root,kv.key);
            if(index!=-1){
                root.keyAndValues.get(index).setValue(kv.value);
                return;
            }
            //不在节点中，且节点有位置，插入
            if(root.keyAndValues.size()<order){
                //System.out.println("227-不在节点中，且节点有位置，插入");
                inseartInleaf(root,kv);
                return;
            }
            //不在节点中且节点已满，先插入进去，再分裂为两个节点
            //左边的继承整除2的一半（比如3个继承（3+1）/2=2个，4个继承（4+1）/2=2个）
            //System.out.println("231-不在节点中且节点已满，先插入进去，再分裂为两个节点");
            inseartInleaf(root,kv);
            int leftsize=root.keyAndValues.size()/2;
            Node left=new Node(true);
            Node right=new Node(true);
            for(int i=0;i<leftsize;i++){
                left.keyAndValues.add(root.keyAndValues.get(i));
            }
            for(int i=0;i<leftsize;i++){
                right.keyAndValues.add(root.keyAndValues.get(leftsize+i));
            }
            //调整指针（连接）；
            if(root.preNode==null){
                //System.out.println("246-");
                this.head=left;
            }
            else{
                left.preNode=root.preNode;
                root.preNode.nextNode=left;
            }
            if(root.nextNode!=null){
                root.nextNode.preNode=right;
                right.nextNode=root.nextNode;
            }
            left.nextNode=right;
            right.preNode=left;
            root.preNode=null;
            root.nextNode=null;
            //调整父节点；
            //如果不是根节点，//找到父节点中root的位置x,删除，分别在x上插入，right,left
            if(root.fatherNode!=null){
                //System.out.println("262-如果不是根节点，//找到父节点中root的位置x,删除，分别在x上插入，right,left");
                //调整子节点列表
                int index2=root.fatherNode.children.indexOf(root);
                left.fatherNode=root.fatherNode;
                right.fatherNode=root.fatherNode;
                root.fatherNode.children.remove(index2);
                //System.out.println("274-"+index2);
                root.fatherNode.children.add(index2,right);
                root.fatherNode.children.add(index2,left);
                //调整键表
                int index3=0;
                if(root.isLeaf()) {
                    root.fatherNode.keyList.add(right.keyAndValues.get(0).key);
                    Collections.sort(root.fatherNode.keyList,new TreeNodeComparator());
                }else{
                    index3=root.fatherNode.keyList.indexOf(root.keyList.get(0));
                    if(index3>=0){
                        root.fatherNode.keyList.remove(index3);
                        root.fatherNode.keyList.add(index3,right.keyList.get(0));
                        root.fatherNode.keyList.add(index3,left.keyList.get(0));
                        Collections.sort(root.fatherNode.keyList,new TreeNodeComparator());
                    }
                    else{
                        root.fatherNode.keyList.add(right.keyList.get(0));
                        Collections.sort(root.fatherNode.keyList,new TreeNodeComparator());
                        //root.fatherNode.keyList.add(left.keyList.get(0));
                    }
                }
                //System.out.println("276-"+root.fatherNode.keyList);
                //System.out.println("277-"+root.fatherNode.children.size());
                //向上回溯，调整父节点
                updateInseart(root.fatherNode);
                root.fatherNode=null;
            }
            else{
                //System.out.println("287-调节父节点指针，父节点为根");
                Node newNode=new Node(false);
                this.root=newNode;
                left.fatherNode=newNode;
                right.fatherNode=newNode;
                newNode.children.add(left);
                newNode.children.add(right);
                if(right.isLeaf()){
                    newNode.keyList.add(right.keyAndValues.get(0).key);
                    Collections.sort(newNode.keyList,new TreeNodeComparator());
                }
                else{
                    newNode.keyList.add(right.keyList.get(0));
                    Collections.sort(newNode.keyList,new TreeNodeComparator());
                }
                //System.out.println("308-"+newNode.keyList);
                //System.out.println(newNode.keyList);
                //System.out.println(newNode.children);
                if(root.isLeaf())
                    root.keyAndValues=null;
            }
            return;
        }
        //不是叶子节点，遍历找到叶子节点
        //非叶子节点
        //如果key小于最左边的key,沿着第一个子节点继续搜索
        if(kv.key-root.keyList.get(0)<0)
            inseart(root.children.get(0),kv);
            //如果key大于等于最右边ke'y，沿着最后一个子节点继续搜索
        else if(kv.key-root.keyList.get(root.keyList.size()-1)>=0){
            //System.out.println("303-"+root.children);
            //System.out.println("304-"+root.children.get(root.children.size()-1).keyAndValues.size());
            inseart(root.children.get(root.children.size()-1),kv);

        }
        //否则沿比key大的前一个子节点继续搜索
        else{
            //二分查找，
            int low=0,high=root.keyList.size()-1,mid=0;
            int comp;
            while(low<=high){
                mid=(low+high)/2;
                comp=root.keyList.get(mid)-kv.key;
                if(comp==0)
                    inseart(root.children.get(mid+1),kv);
                else if(comp<0)
                    low=mid+1;
                else
                    high=mid-1;
            }
            inseart(root.children.get(low),kv);
        }
    }

    //插入节点后回溯更新父节点
    private void updateInseart(Node root){
        //System.out.println("329父节点子节点链表长："+root.children.size()+" order: "+order);
        if(root.children.size()>order){
            int rightsize=root.children.size()/2+root.children.size()%2;
            int leftsize=root.children.size()/2;
            //System.out.println("335-leftsize:"+leftsize);
            Node left=new Node(false);
            Node right=new Node(false);
            for(int i=0;i<leftsize;i++){
                left.children.add(root.children.get(i));
                root.children.get(i).fatherNode=left;
            }
            for(int i=0;i<rightsize;i++){
                right.children.add(root.children.get(leftsize+i));
                root.children.get(leftsize+i).fatherNode=right;
            }
            //System.out.println("346-"+right.children.size());

            for(int i=0;i<leftsize-1;i++){
                left.keyList.add(root.keyList.get(i));
            }
            for(int i=0;i<rightsize-1;i++){
                right.keyList.add(root.keyList.get(leftsize+i));
            }
            //System.out.println("372-"+left.keyList);
            //System.out.println("373-"+right.keyList);
            //System.out.println("374-"+left.children.get(0).fatherNode);
            //System.out.println("375-"+right.preNode.keyList);
            //System.out.print("377-");
            //System.out.println(root.fatherNode!=null);
            //如果不是根节点
            if(root.fatherNode!=null){
                //调整子节点列表
                int index2=root.fatherNode.children.indexOf(root);
                left.fatherNode=root.fatherNode;
                right.fatherNode=root.fatherNode;
                root.fatherNode.children.remove(index2);
                root.fatherNode.children.add(index2,right);
                root.fatherNode.children.add(index2,left);
                //调整键表
                int index3=0;
                if(root.isLeaf()) {
                    root.fatherNode.keyList.add(right.keyAndValues.get(0).key);
                    Collections.sort(root.fatherNode.keyList,new TreeNodeComparator());
                }else{
                    index3=root.fatherNode.keyList.indexOf(root.keyList.get(0));
//                    System.out.println("413-index3 "+index3);
//                    System.out.println("414-index3 "+root.fatherNode.keyList);
//                    System.out.println("415-index3 "+root.keyList.get(0));
                    if(index3>=0){
                        root.fatherNode.keyList.remove(index3);
                        root.fatherNode.keyList.add(index3,right.keyList.get(0));
                        root.fatherNode.keyList.add(index3,left.keyList.get(0));
                        Collections.sort(root.fatherNode.keyList,new TreeNodeComparator());
                    }
                    else{
                        root.fatherNode.keyList.add(right.keyList.get(0));
                        Collections.sort(root.fatherNode.keyList,new TreeNodeComparator());
                        //root.fatherNode.keyList.add(left.keyList.get(0));
                    }

                }
                //System.out.println("393-"+root.keyList);
                //System.out.println("394-index3 "+index3);
                //root.fatherNode.keyList.add(index3,root.keyList.get(leftsize-1));
                //System.out.println("388-"+root.fatherNode.keyList);
                //向上回溯，调整父节点
                updateInseart(root.fatherNode);
                root.fatherNode=null;
            }else{
                Node newNode=new Node(false);
                this.root=newNode;
                left.fatherNode=newNode;
                right.fatherNode=newNode;
                newNode.children.add(left);
                newNode.children.add(right);
                newNode.keyList.add(root.keyList.get(leftsize-1));
                Collections.sort(newNode.keyList,new TreeNodeComparator());
                root.keyAndValues=null;
                //root.fatherNode=null;
            }

        }

    }

    /**
     * 删除
     * 当非叶子节点子节点列表<order/2或者<2,需要合并节点
     */
    public void delete(Node root,int key){
        //键不在树中
        Object result=this.search(key,this.root);
        if(result==null){
            System.out.println("键不在树中，无法删除");
            return;
        }
        //键在树中
        //如果是叶子节点
        if(root.isLeaf()) {
            int index = isExist(root, key);
            //①如果是叶子节点,且是根节点-直接删
            if (root.fatherNode == null) {
                root.keyAndValues.remove(index);
                return;
            }
            //②如果删后不需要合并节点，直接删
            if (root.keyAndValues.size() > order / 2 && root.keyAndValues.size() > 2) {
                root.keyAndValues.remove(index);
                return;
            }
            //③如果自身关键字数数=order/2(小于order/2的情况应该不存在，删除后就不平衡了)且，
            // 前一个节点关键字数>2，则从前面借一个在删
            if(root.preNode!=null&&root.preNode.fatherNode==root.fatherNode&&root.preNode.keyAndValues.size()>order/2&&root.preNode.keyAndValues.size()>2){
                int index1=root.preNode.keyAndValues.size();
                root.keyAndValues.add(0,root.preNode.keyAndValues.remove(index1-1));
                int index2=root.fatherNode.children.indexOf(root.preNode);
                root.fatherNode.keyList.set(index2,root.keyAndValues.get(0).key);
                //新增了一个节点index+1
                root.keyAndValues.remove(index+1);
                return;
            }
            //④如果自身关键字数数=order/2(小于order/2的情况应该不存在，删除后就不平衡了)且，
            // 后一个节点关键字数>2，则从后面借一个在删
            if(root.nextNode!=null&&root.nextNode.fatherNode==root.fatherNode&&root.nextNode.keyAndValues.size()>order/2&&root.nextNode.keyAndValues.size()>2){
                root.keyAndValues.add(root.nextNode.keyAndValues.remove(0));
                int index3=root.fatherNode.children.indexOf(root);
                root.fatherNode.keyList.set(index3,root.nextNode.keyAndValues.get(0).key);
                //尾部添加，index不变
                root.keyAndValues.remove(index);
                return;
            }

            //⑤上述不成立即借不到节点，只能自己合并给别人了
            //前节点非空，与前节点合并
            if(root.preNode!=null&&root.preNode.fatherNode==root.fatherNode
                    &&(root.preNode.keyAndValues.size()<=order/2||root.preNode.keyAndValues.size()<=2)){
                root.keyAndValues.remove(index);
                for(int i=0;i<root.keyAndValues.size();i++){
                    root.preNode.keyAndValues.add(root.keyAndValues.get(i));
                }
                root.keyAndValues=root.preNode.keyAndValues;
                root.fatherNode.children.remove(root.preNode);
                root.preNode.fatherNode=null;
                root.preNode.keyAndValues=null;
                //更新链表
                if(root.preNode.preNode!=null){
                    Node p=root.preNode;
                    p.preNode.nextNode=root;
                    root.preNode=p.preNode;
                    p.preNode=null;
                    p.nextNode=null;
                }else{
                    this.head=root;
                    root.preNode.nextNode=null;
                    root.preNode=null;
                }
                //如果父节点符合平衡，退出
                root.fatherNode.keyList.remove(root.fatherNode.children.indexOf(root));
                if((root.fatherNode.fatherNode!=null&&(root.fatherNode.children.size()>=order/2&&root.fatherNode.children.size()>=2))||root.fatherNode.fatherNode==null&&root.fatherNode.children.size()>=2){
                    return;
                }
                //回溯更新父节点
                updateDelete(root.fatherNode);
                return;
            }

            //⑥到这一步说明前阶段空了
            //同后节点合并。
            if(root.nextNode!=null&&root.nextNode.fatherNode==root.fatherNode&&(root.nextNode.keyAndValues.size()<=order/2||root.nextNode.keyAndValues.size()<=2)){
                root.keyAndValues.remove(index);
                for(int i=0;i<root.nextNode.keyAndValues.size();i++){
                    root.keyAndValues.add(root.keyAndValues.get(i));
                }
                root.nextNode.fatherNode=null;
                root.nextNode.keyAndValues=null;
                root.fatherNode.children.remove(root.nextNode);
                //更新链表
                if(root.nextNode.nextNode!=null){
                    Node p=root.nextNode;
                    p.nextNode.preNode=root;
                    root.nextNode=p.nextNode;
                    p.preNode=null;
                    p.nextNode=null;
                }else{
                    root.preNode=null;
                    root.nextNode=null;
                }
                //更新父节点链表
                root.fatherNode.keyList.remove(root.fatherNode.children.indexOf(root));
                if((root.fatherNode.fatherNode!=null&&(root.fatherNode.children.size()>=order/2&&root.fatherNode.children.size()>=2))||root.fatherNode.fatherNode==null&&root.fatherNode.children.size()>=2){
                    return;
                }
                updateDelete(root.fatherNode);
                return;
            }

        }
        //如果不是叶子节点，就遍历到叶子节点
        //非叶子节点
        //如果key小于最左边的key,沿着第一个子节点继续搜索
        if(key-root.keyList.get(0)<0)
            delete(root.children.get(0),key);
            //如果key大于等于最右边ke'y，沿着最后一个子节点继续搜索
        else if(key-root.keyList.get(root.keyList.size()-1)>=0){
            //System.out.println(root.keyList);
            delete(root.children.get(root.children.size()-1),key);
        }
        //否则沿比key大的前一个子节点继续搜索
        else{
            //二分查找，
            int low=0,high=root.keyList.size()-1,mid=0;
            int comp;
            while(low<=high){
                mid=(low+high)/2;
                comp=root.keyList.get(mid)-key;
                if(comp==0)
                    delete(root.children.get(mid+1),key);
                else if(comp<0)
                    low=mid+1;
                else
                    high=mid-1;
            }
            delete(root.children.get(low),key);
        }

    }

    //删除后回溯更新-平衡
    private void updateDelete(Node root){
        //如果节点<order/2或者<小于2，
        if(root.children.size()<order/2||root.children.size()<2){
            if(root.fatherNode==null){
                if(root.children.size()>2)
                    return;
                Node p=root.children.get(0);
                this.root=p;
                p.fatherNode=null;
                root.keyList=null;
                root.keyList=null;
                return;
            }
            //计算前后节点
            int currIdx=root.fatherNode.children.indexOf(root);
            int preIdx=currIdx-1;
            int nextIdx=currIdx+1;
            Node preNode=null,nextNode=null;
            if(preIdx>=0)
                preNode=root.fatherNode.children.get(preIdx);
            if(nextIdx<root.fatherNode.children.size())
                nextNode=root.fatherNode.children.get(nextIdx);


            // 前一个节点关键字数>2，则从前面借一个在删
            if(preNode!=null&&preNode.children.size()>order/2&&preNode.children.size()>2){
                int index1=preNode.children.size()-1;
                Node borrow=preNode.children.get(index1);
                preNode.children.remove(index1);
                borrow.fatherNode=root;
                root.children.add(0,borrow);

                int index2=root.fatherNode.children.indexOf(preNode);
                root.keyList.add(0,root.fatherNode.keyList.get(index2));
                root.fatherNode.keyList.set(index2,preNode.keyList.remove(index1-1));
                return;
            }
            //④如果自身关键字数数=order/2(小于order/2的情况应该不存在，删除后就不平衡了)且，
            // 后一个节点关键字数>2，则从后面借一个在删
            if(nextNode!=null&&nextNode.children.size()>order/2&&nextNode.children.size()>2){
                Node borrow=nextNode.children.get(0);
                nextNode.children.remove(0);
                borrow.fatherNode=root;
                root.children.add(borrow);
                int index3=root.fatherNode.children.indexOf(root);
                root.keyList.add(root.fatherNode.keyList.get(index3));
                root.fatherNode.keyList.set(index3,nextNode.keyList.remove(0));
                return;
            }

            //⑤上述不成立即借不到节点，只能自己合并给别人了
            //前节点非空，与前节点合并
            if(preNode!=null&&(preNode.children.size()<=order/2||preNode.children.size()<=2)){
                for(int i=0;i<root.children.size();i++){
                    preNode.children.add(root.children.get(i));
                }
                for(int i=0;i<preNode.children.size();i++){
                    preNode.children.get(i).fatherNode=root;
                }
                int indexPre=root.fatherNode.children.indexOf(preNode);
                preNode.keyList.add(root.fatherNode.keyList.get(indexPre));
                for(int i=0;i<root.keyList.size();i++){
                    preNode.keyList.add(root.keyList.get(i));
                }
                root.children=preNode.children;
                root.keyList=preNode.keyList;

                root.fatherNode.children.remove(preNode);
                preNode.fatherNode=null;
                preNode.keyList=null;
                preNode.children=null;
                root.fatherNode.keyList.remove(root.fatherNode.children.indexOf(root));
                //更新链表
                if((root.fatherNode.fatherNode!=null&&(root.fatherNode.children.size()>=order/2&&root.fatherNode.children.size()>=2))
                        ||root.fatherNode.fatherNode==null&&root.fatherNode.children.size()>=2){
                    return;
                }
                //回溯更新父节点
                updateDelete(root.fatherNode);
                return;
            }

            //⑥到这一步说明前阶段空了
            //同后节点合并。
            if(nextNode!=null&&(nextNode.children.size()<=order/2||nextNode.children.size()<=2)){
                for(int i=0;i<nextNode.children.size();i++){
                    Node child=nextNode.children.get(i);
                    root.children.add(child);
                    child.fatherNode=root;
                }
                int index=root.fatherNode.children.indexOf(root);
                root.keyList.add(root.fatherNode.keyList.get(index));
                for(int i=0;i<nextNode.keyList.size();i++){
                    root.keyList.add(nextNode.keyList.get(i));
                }

                root.fatherNode.children.remove(nextNode);
                nextNode.fatherNode=null;
                nextNode.keyList=null;
                nextNode.children=null;
                root.fatherNode.keyList.remove(root.fatherNode.children.indexOf(root));
                //更新链表
                if((root.fatherNode.fatherNode!=null&&(root.fatherNode.children.size()>=order/2&&root.fatherNode.children.size()>=2))
                        ||root.fatherNode.fatherNode==null&&root.fatherNode.children.size()>=2){
                    return;
                }
                updateDelete(root.fatherNode);
                return;
            }
        }
    }

    /**
     * 打印
     */
    private int height(Node root){
        if(root==null)
            return 0;
        if(root.isLeaf())
            return 1;
        int height=1;
        do{
            root=root.children.get(0);
            height++;
        }while(!root.isLeaf());
        return height;
    }
    private void printTree(Node root,Node head){
        int H=height(root);
        int h=H;
        //System.out.println("树高："+H);
        if(H==0){
            System.out.println("树空,无打印");
            return;
        }
        else{
            //System.out.println("446-H=="+H);
            System.out.println("打印树：");
            Queue<Node> queue=new LinkedList<>();
            queue.add(root);
            //记录每层孩子个数
            int len=1;
            while(h>0){
                int length=0;
                for(int i=0;i<len;i++){
                    Node curroot=queue.poll();
                    if(curroot.isLeaf()){
                        for(int j=0;j<curroot.keyAndValues.size();j++){
                            System.out.print(curroot.keyAndValues.get(j).key+",");
                        }
                    }else{
                        //System.out.println("根节点键表长 "+curroot.children.size());
                        //System.out.println("462-"+curroot.keyList.size());
                        for(int j=0;j<curroot.keyList.size();j++){
                            System.out.print(curroot.keyList.get(j)+",");
                        }
                        for(int j=0;j<curroot.children.size();j++){
                            queue.add(curroot.children.get(j));
                            length++;
                        }
                    }
                    System.out.println();
                }
                System.out.println();
                len=length;
                h--;
            }
        }
        //输出叶子节点value
//        Node h1=head;
//        while(h1!=null){
//            for(int i=0;i<h1.keyAndValues.size();i++)
//                System.out.print(h1.keyAndValues.get(i).value+"-");
//            h1=h1.nextNode;
//            System.out.print("|");
//        }
//        System.out.print("\n");
    }


    public static void main(String args[]) {
        KeyAndValue keyAndValue1 = new KeyAndValue(1,"1");
        KeyAndValue keyAndValue2 = new KeyAndValue(2,"1");
        KeyAndValue keyAndValue3 = new KeyAndValue(3,"2");
        KeyAndValue keyAndValue4 = new KeyAndValue(4,"3");
        KeyAndValue keyAndValue5 = new KeyAndValue(5,"3");
        KeyAndValue keyAndValue6 = new KeyAndValue(6,"1");
        KeyAndValue keyAndValue7 = new KeyAndValue(7,"1");
        KeyAndValue keyAndValue8 = new KeyAndValue(8,"5");
        KeyAndValue keyAndValue9 = new KeyAndValue(9,"1");
        KeyAndValue keyAndValue10 = new KeyAndValue(10,"3");
        KeyAndValue keyAndValue11 = new KeyAndValue(11,"2");
        KeyAndValue keyAndValue12 = new KeyAndValue(12,"2");
        KeyAndValue keyAndValue13 = new KeyAndValue(13,"2");
        KeyAndValue keyAndValue14 = new KeyAndValue(14,"1");
        KeyAndValue keyAndValue15 = new KeyAndValue(15,"1");
        KeyAndValue keyAndValue16 = new KeyAndValue(16,"1");
        KeyAndValue keyAndValue17 = new KeyAndValue(17,"1");
        KeyAndValue keyAndValue18 = new KeyAndValue(18,"1");
        KeyAndValue keyAndValue19 = new KeyAndValue(19,"4");
        KeyAndValue keyAndValue20 = new KeyAndValue(20,"5");
        KeyAndValue keyAndValue21 = new KeyAndValue(21,"5");
        KeyAndValue keyAndValue22 = new KeyAndValue(22,"5");
        KeyAndValue keyAndValue23 = new KeyAndValue(23,"5");
        KeyAndValue keyAndValue24 = new KeyAndValue(24,"5");
        BPlusTree t=new BPlusTree(3);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue1);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue3);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue22);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue6);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue17);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue15);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue24);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue19);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue2);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue5);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue20);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue18);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue7);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue4);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue21);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue11);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue12);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue9);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue10);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue13);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue14);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue8);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue16);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue23);
        t.printTree(t.root,t.head);
        t.inseart(t.root,keyAndValue23);
        t.printTree(t.root,t.head);


        t.delete(t.root,23);
        t.printTree(t.root,t.head);
        t.delete(t.root,3);
        t.printTree(t.root,t.head);
        t.delete(t.root,14);
        t.printTree(t.root,t.head);
        t.delete(t.root,13);
        t.printTree(t.root,t.head);
        t.delete(t.root,12);
        t.printTree(t.root,t.head);
        t.delete(t.root,8);
        t.printTree(t.root,t.head);
        t.delete(t.root,18);
        t.printTree(t.root,t.head);
        t.delete(t.root,22);
        t.printTree(t.root,t.head);
        t.delete(t.root,1);
        t.printTree(t.root,t.head);
        t.delete(t.root,2);
        t.printTree(t.root,t.head);
        t.delete(t.root,4);
        t.printTree(t.root,t.head);


        //System.out.println("search13: "+t.search(33,t.root));

    }

}